This application claims the benefit of a Japanese Patent Application No. 11-342306 filed Dec. 1, 1999, in the Japanese Patent Office, the disclosure of which is hereby incorporated by reference.
1. Field of the Invention
The present invention generally relates to path determination methods and storage media, and more particularly to a path determination method for automatically determining a path such as a wiring route within a wiring region, a communication route within a communication network and a moving route within a transportation system, and to a computer-readable storage medium which stores a program for causing a computer to automatically determine a path by such a path determination method.
Conventionally, there are techniques which use a computer to automatically determine a path, such as a wiring route within a wiring region of a semiconductor integrated circuit or a printed circuit, a communication route within a communication network, and a moving route within a transportation system. Various wiring techniques for determining the wiring route, various routing techniques for determining the communication route, and various navigation techniques for determining a moving route have been proposed.
2. Description of the Related Art
For example, the design of the wirings within the wiring region of the semiconductor integrated circuit or the printed circuit is becoming increasingly difficult due to the recent improvements in the integration density of circuits and circuit elements. For this reason, the wiring routes of large scale integrated (LSI) circuits and the like are determined by an automatic wiring technique which uses computer aided design (CAD).
According to the automatic wiring technique, the wirings are determined starting from an arbitrary wiring. If the wirings overlap, the designer manually searches for a wiring route which will not overlap with another wiring route, and corrects the overlapping wiring route by rerouting the wiring route. Accordingly, in the case of the LSI circuit or the like, it requires a skilled designer to correct the wiring route in such a manner, because a plurality of wiring layers exist and the wiring is extremely complex. In addition, it takes considerable time for the designer to correct the wiring route in such a manner, and as a result, it takes a long time to determine the final wiring route.
Furthermore, a wiring route between two points within the wiring region has a tendency of concentrating at a specific portion of the wiring region. Generally, the wiring routes concentrate more at a central portion of the wiring region than at other portions of the wiring region. But when the wiring routes are locally concentrated within the wiring region, the probability of overlapping wirings increases, and a wiring success rate decreases. The wiring success rate indicates a rate at which the wirings are successfully routed without overlap. Accordingly, the designer must frequently carry out the operation of manually searching for the wiring route which will not overlap with other wiring routes and correct the overlapping wiring route by rerouting the wiring route.
However, when the wiring routes are locally concentrated, there are cases where an appropriately rerouted wiring route cannot be provided as the number of wiring routes increases, due to the local concentration of the wiring routes within the wiring region, even if unused portions where the wiring routes can be provided still exist within the wiring region. In such cases, it is necessary to greatly modify the wiring design, and there is a problem in that it takes an extremely long time to carry out the wiring design.
In addition, the local concentration of the wiring routes can only be managed by the designer. As a result, the utilization efficiency of the wiring region is entirely dependent on the skills and experiences of the designer. Hence, there is a problem in that it is difficult to maintain the utilization efficiency of the wiring region above a predetermined value regardless of the level of skills and experiences of the designer. On the other hand, as the number of wiring routes increases, the wiring success rate decreases, and it is becoming virtually impossible for the designer to satisfactorily carry out the operations such as managing the local concentration of the wiring routes and providing appropriately rerouted wiring routes.
The problems described above are not peculiar to the wiring technique which determines the wiring route. Similar problems also occur in the case of the routing technique which determines the communication route, and the navigation technique which determines the moving route. In other words, the communication routes have the tendency of locally concentrating in the case of the communication network, and the moving routes have the tendency of locally concentrating in the case of the transportation system. For this reason, there are not only demands to solve the problems described above with respect to the wiring technique which determines the wiring route, but also to realize a routing technique which can determine the communication route within the communication network within a short time at a high success rate, and to realize a navigation technique which can determine the moving route within the transportation system within a short time at a high success rate.
Accordingly, it is a general object of the present invention to provide a novel and useful path determination method and computer-readable storage medium, in which the problems described above are eliminated.
Another and more specific object of the present invention is to provide a path determination method and a computer-readable storage medium, which can determine a path within a path determination region in which the path is to be determined, within a short time at a high success rate, and improve the utilization efficiency of the path determination region.
Still another object of the present invention is to provide a path determination method comprising the steps of (a) determining a path in a first region which has a utilization efficiency less than a predetermined value probability-wise, (b) determining a path in a second region which is different from the first region when the utilization efficiency of the first region exceeds a second predetermined value, where the second region has a utilization efficiency exceeding the first predetermined value probability-wise, (c) dividing an entire region which is to be subjected to a path determination into partial regions of predetermined sizes and using the partial regions as a minimum unit of path search, (d) assigning to each of the partial regions a state quantity which is described by a path accommodating capacity within each of the partial regions, and (e) searching a path between two points by controlling a search speed depending on a change in the state quantity between adjacent partial regions. According to the path determination method of the present invention, it is possible to determine a path within a path determination region in which the path is to be determined, within a short time at a high success rate, and improve the utilization efficiency of the path determination region.
The state quantity may be formed by a heat capacity. In addition, the region which is to be subjected to the path determination may be formed by a wiring region, the path may be formed by a wiring route within the wiring region, and one of the partial regions may be determined by two terminals within the wiring region. In this case, it is possible to improve the wiring technique for determining the wiring within integrated circuits, wiring boards and the like.
The path may be formed by a communication route within a communication network, one of the partial regions may be determined by two nodes within the communication network, and the state quantity may be formed by a band of the communication network. In this case, it is possible to improve the routing technique for determining the communication route within the communication system.
The path may be formed by a moving route within a transportation system, one of the partial regions may be determined by an entrance point and an exit point within the transportation system, and the state quantity may be formed by a width of the moving path within the transportation system. In this case, it is possible to improve the navigation technique for determining the moving route within the transportation system.
A further object of the present invention is to provide a computer-readable storage medium which stores a program for causing a computer to determine a path, comprising means for causing the computer to determine a path in a first region which has a utilization efficiency less than a predetermined value probability-wise, means for causing the computer to determine a path in a second region which is different from the first region when the utilization efficiency of the first region exceeds a second predetermined value, where the second region has a utilization efficiency exceeding the first predetermined value probability-wise, means for causing the computer to divide an entire region which is to be subjected to a path determination into partial regions of predetermined sizes and using the partial regions as a minimum unit of path search, means for causing the computer to assign to each of the partial regions a state quantity which is described by a path accommodating capacity within each of the partial regions, and means for causing the computer to search a path between two points by controlling a search speed depending oh a change in the state quantity between adjacent partial regions. According to the computer-readable storage medium of the present invention, it is possible to determine a path within a path determination region in which the path is to be determined, within a short time at a high success rate, and improve the utilization efficiency of the path determination region.
Other objects and further features of the present invention will be apparent from the following detailed description when read in conjunction with the accompanying drawings.